Problem statement: zenit15ckg

Gaudeamus igitur

Počet bodov: 35, časový limit: 2000ms

Ako ste si určite všimli, mnohých učiteľov prestala baviť situácia v školstve a rozhodli sa vyjsť do ulíc. Spravia živú reťaz. Obvolali úrady, políciu, televíziu. Všetko pripravené, no ráno pred reťazením si spomenuli na jednu dôležitú maličkosť.

Nikto z učiteľov totiž nevedel, kade reťaz povedie. Miesto na demonštráciu už majú vyhradené, reťaziť sa môžu na \(n\) križovatkách a uliciach rôznej dĺžky, ktorými sú prepojené. Medzi dvoma križovatkami vedie najviac jedna ulica. Učitelia chcú mať reťaz čo najdlhšiu, no nechcú, aby prechádzala tou istou križovatkou viackrát. Takisto chcú, aby prechádzala popred Úrad vlády. Potrebujú vašu pomoc.

Úloha

Dostanete zadaný neorientovaný ohodnotený graf. Križovatky predstavujú vrcholy, ulice hrany. Úrad vlády je na križovatke s číslom 1. Vašou úlohou je teda nájsť najdlhšiu kružnicu v grafe prechádzajúcu vrcholom číslo 1.

Vstup a výstup

Na prvom riadku dostanete 2 medzerou oddelené čísla. \(n\) – počet križovatiek \((1 \leq n \leq 20)\) a \(m\) – počet ulíc.

Na nasledujúcich \(m\) riadkoch dostanete medzerou oddelené čísla \(x_i, y_i, l_i\) – križovatky na konci \(i\)-tej ulice a jej dĺžku. \(1 \leq x_i,\, y_i \leq n\), \(1 \leq l_i \leq 1\,000\)

Vrcholy sú číslované od \(1\) po \(n\) vrátane!

Vypíšte jedno číslo – dĺžku najdlhšej reťaze, akú vedia učitelia vytvoriť. Riešenia v pomalších jazykoch (Pythone) pravdepodobne nemajú šancu stíhať najväčšie vstupy.

Príklad

Input:

4 5
1 2 10
1 3 20
2 4 15
3 4 1
1 4 5

Output:

46

Najdlhšia reťaz prechádza vrcholmi 1, 2, 4, 3 a potom sa vracia späť do 1.